/*
 * @lc app=leetcode.cn id=15 lang=javascript
 *
 * [15] 三数之和
 *
 * https://leetcode-cn.com/problems/3sum/description/
 *
 * algorithms
 * Medium (23.20%)
 * Likes:    1176
 * Dislikes: 0
 * Total Accepted:    73K
 * Total Submissions: 313.9K
 * Testcase Example:  '[-1,0,1,2,-1,-4]'
 *
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0
 * ？找出所有满足条件且不重复的三元组。
 * 
 * 注意：答案中不可以包含重复的三元组。
 * 
 * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 * 
 * 满足要求的三元组集合为：
 * [
 * ⁠ [-1, 0, 1],
 * ⁠ [-1, -1, 2]
 * ]
 * 
 * 
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
    let re = []
    if (nums === null || nums.length < 3) return re
    nums.sort((a, b) => a - b)
    for (let i = 0; i < nums.length; i++) {
        let a = nums[i]
        if (a > 0) break
        if (i > 0 && nums[i] === nums[i - 1]) continue
        let p1 = i + 1
        let p2 = nums.length - 1
        let target = 0 - a
        while (p1 < p2) {
            let sum = nums[p1] + nums[p2]
            if (sum === target) {
                re.push([a, nums[p1], nums[p2]])
                while (p1 < p2 && nums[p1] === nums[p1 + 1]) p1++
                while (p1 < p2 && nums[p2] === nums[p2 - 1]) p2--
                p1++
                p2--
            } else if (sum < target) p1++
            else p2--
        }
    }
    return re
};

console.log(threeSum([-1, 0, 1, 2, -1, -4]))